package com.milo.list;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 过滤数组中重复的元素
 * @author milogenius
 * @date 2020/4/22 23:03
 */
public class DuplicatesFromArray {
    public static void main(String args[]) {
        int[] withDuplicates = { 1, 2, 3, 1, 2, 3, 4, 5, 3, 6 };
        //调用常规方法
        Set<Integer> duplicates = findDuplicates(withDuplicates);
        System.out.println("input array is : " + Arrays.toString(withDuplicates));
        System.out.println("Duplicate elements found in array are : " + duplicates);

        // 调用泛型方法
        String[] myArray = { "ab", "cd", "ab", "de", "cd" };
        System.out.println("input string array is : " + Arrays.toString(myArray));
        getDuplicates(myArray);
    }

    /**
     * 时间复杂度是O(n²)
     *
     * @param input
     * @return
     */
    public static Set<Integer> findDuplicates(int[] input) {
        Set<Integer> duplicates = new HashSet<Integer>();

        for (int i = 0; i < input.length; i++) {
            for (int j = 1; j < input.length; j++) {
                if (input[i] == input[j] && i != j) {
                    // 发现重复元素
                    duplicates.add(input[i]);
                    break;
                }
            }
        }

        return duplicates;
    }

    /**
     * 时间复杂度为O(n) ,因为我们使用了HashSet数据结构
     *
     * @param array
     * @return
     */
    public static <T extends Comparable<T>> void getDuplicates(T[] array) {
        Set<T> dupes = new HashSet<T>();
        for (T i : array) {
            if (!dupes.add(i)) {
                System.out.println("Duplicate element in array is : " + i);
            }
        }

    }


}
